// https://leetcode-cn.com/problems/lfu-cache/
/**
 * @param {number} capacity
 */
var LFUCache = function(capacity) {
  this.capacity = capacity;
  this.sortList = {};
  // 解决长度问题
  this.map = {
    length: 0,
  };
  // 获取使用量最少的key
  this.minSort = 0;
};

/**
 * @param {number} key
 * @return {number}
 */
LFUCache.prototype.get = function(key) {
  if (this.map[key] === void 0) return -1;
  // 当前key被使用一次就+1
  this.updateList(key);
  return this.map[key].value;
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LFUCache.prototype.put = function(key, value) {
  if (this.capacity === 0) return;
  if (this.map[key] !== void 0) {
    this.map[key].value = value;
    this.updateList(key);
    return;
  }
  // 判断是否需要清除缓存
  if (this.map.length >= this.capacity) {
    // 获取最近添加的使用较少的key
    for (let item of this.sortList[this.minSort].keys()) {
      this.sortList[this.minSort].delete(item);
      if (this.sortList[this.minSort].size <= 0) this.minSort++;
      delete this.map[item];
      this.map.length--;
      break
    }

  }
  // 初始化sortList
  this.sortList['0'] || (this.sortList['0'] = new Set());
  this.sortList['0'].add(key);
  this.map[key] = {
    value,
    sort: 0,
  };
  this.minSort = 0;
  this.map.length++;
};
LFUCache.prototype.updateList = function(key) {
  // 先删除原来的
  this.sortList[this.map[key].sort].delete(key);
  this.sortList[++this.map[key].sort] ||
  (this.sortList[this.map[key].sort] = new Set());
  this.sortList[this.map[key].sort].add(key);
  if (this.sortList[this.minSort].size <= 0) this.minSort++;
};
/**
 * Your LFUCache object will be instantiated and called as such:
 * var obj = new LFUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */
let cache = null;
let a =  ["LFUCache","put","put","get","put","get","get","put","get","get","get"]
let b = [[2],[1,1],[2,2],[1],[3,3],[2],[3],[4,4],[1],[3],[4]]
a.forEach((item, index) => {
  switch (item) {
    case "LFUCache" :
      cache = new LFUCache(...b[index])
      break
    case "put" :
      cache.put(...b[index])
      break
    case "get" :
      console.log(cache.get(...b[index]), cache.map);
      break;
  }
})